from math import sqrt
from typing import List


class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        # 递归求阶乘
        def factorial(n) -> int:
            if (n <= 1):
                return 1
            return n * factorial(n - 1)

        # 定义质数，这里要多取以为，用来终止循环并且防止索引越界
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101]

        # 计算质数的数量
        primeCount = 0
        while (primes[primeCount] <= n):
            primeCount += 1
        # 质数的阶乘乘以和数的阶乘
        return factorial(primeCount) * factorial(n - primeCount) % (10 ** 9 + 7)

if __name__ == '__main__':
    nums = [8308, 8308, 830]
    solution = Solution()
    print(solution.numPrimeArrangements(5))
